Min-degree constrained minimum spanning tree problem: New formulation via Miller–Tucker–Zemlin constraints

Given an undirected network with positive edge costs and a positive integer $d>2$, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least $d$. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller–Tucker–Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller–Tucker–Zemlin constraints.     

A quick tour on suffix arrays and compressed suffix arrays

Suffix arrays are a key data structure for solving a run of problems on texts and sequences, from data compression and information retrieval to biological sequence analysis and pattern discovery. In their simplest version, they can just be seen as a permutation of the elements in {1,2,…,n}, encoding the sorted sequence of suffixes from a given text of length n, under the lexicographic order. Yet, they are on a par with ubiquitous and sophisticated suffix trees. Over the years, many interesting combinatorial properties have been devised for this special class of permutations: for instance, they can implicitly encode extra information, and they are a well characterized subset of the n! permutations. This paper gives a short tutorial on suffix arrays and their compressed version to explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression.     

基于可能性测度的计算树逻辑

首先,提出了可能的Kripke结构的定义,建立了可能的Kripke结构的可能性测度空间,并分析了可能的Kripke结构的一系列性质,即任一路径转移的可能性可由其初始状态的可能性分布与各转移的可能性取下确界而得到;依据可能的Kripke结构所定义的可能性测度具有其合理性等等。其次,给出了可能性计算树逻辑(PoCTL)的概念,讨论了两个PoCTL状态公式以及PoCTL与经典计算树逻辑(CTL)公式的等价性。最后,证明了PoCTL公式有与CTL*公式中"一致性"相对应的公式。     

Object-based crop identification using multiple vegetation indices, textural features and crop phenology

Crop identification on specific parcels and the assessment of soil management practices are important for agro-ecological studies, greenhouse gas modeling, and agrarian policy development. Traditional pixel-based analysis of remotely sensed data results in inaccurate identification of some crops due to pixel heterogeneity, mixed pixels, spectral similarity, and crop pattern variability. These problems can be overcome using object-based image analysis (OBIA) techniques, which incorporate new spectral, textural and hierarchical features after segmentation of imagery. We combined OBIA and decision tree (DT) algorithms to develop a methodology, named Object-based Crop Identification and Mapping (OCIM), for a multi-seasonal assessment of a large number of crop types and field status.In our approach, we explored several vegetation indices (VIs) and textural features derived from visible, near-infrared and short-wave infrared (SWIR) bands of ASTER satellite scenes collected during three distinct growing-season periods (mid-spring, early-summer and late-summer). OCIM was developed for 13 major crops cultivated in the agricultural area of Yolo County in California, USA. The model design was built in four different scenarios (combinations of three or two periods) by using two independent training and validation datasets and the best DTs resulted in an error rate of 9% for the three-period model and between 12 and 16% for the two-period models. Next, the selected DT was used for the thematic classification of the entire cropland area and mapping was then evaluated applying the confusion matrix method to the independent testing dataset that reported 79% overall accuracy. OCIM detected intra-class variations in most crops attributed to variability from local crop calendars, tree-orchard structures and land management operations. Spectral variables (based on VIs) contributed around 90% to the models, although textural variables were necessary to discriminate between most of the permanent crop-fields (orchards, vineyard, alfalfa and meadow). Features extracted from late-summer imagery contributed around 60% in classification model development, whereas mid-spring and early-summer imagery contributed around 30 and 10%, respectively. The Normalized Difference Vegetation Index (NDVI) was used to identify the main groups of crops based on the presence and vigor of green vegetation within the fields, contributing around 50% to the models. In addition, other VIs based on SWIR bands were also crucial to crop identification because of their potential to detect field properties like moisture, vegetation vigor, non-photosynthetic vegetation and bare soil. The OCIM method was built using interpretable rules based on physical properties of the crops studied and it was successful for object-based feature selection and crop identification.     

Self-stabilizing minimum degree spanning tree within one from the optimal degree

We propose a self-stabilizing algorithm for constructing a Minimum Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Δ^∗+1, where Δ^∗ is the minimum possible maximum degree of a spanning tree of the network.To the best of our knowledge, our algorithm is the first self-stabilizing solution for the construction of a minimum degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e., the send/receive atomicity). The time complexity of our solution is O(mn²logn) where m is the number of edges and n is the number of nodes. The memory complexity is O(δlogn) in the send-receive atomicity model (δ is the maximal degree of the network).     

Estimating residual variance in random forest regression

Random forest, a data-mining technique which uses multiple classification or regression trees, is a popular algorithm used for prediction. Inference and goodness-of-fit assessment, however, may require an estimator of variability; in many applications the residual variance is of primary interest. This paper proposes two estimators of residual variance for random forest regression that take advantage of byproducts of the algorithm. The first estimator is based on the residual sum of squares from a random forest fit and uses a bootstrap bias correction. The second estimator is a difference-based estimator that uses proximity measures as weights. The estimators are evaluated through Monte Carlo simulations. Applications of the methods to the problem of assessing the relative variability of males and females on cognitive and achievement tests are discussed, and the methods are applied to estimate the residual variance in test scores for male and female students on the mathematics portion of the 2007 Arizona Instrument to Measure Standards.     

Use of high-resolution satellite imagery in an integrated model to predict the distribution of shade coffee tree hybrid zones

In New Caledonia (21°S, 165°E), shade-grown coffee plantations were abandoned for economic reasons in the middle of the 20th century. Coffee species (Coffea arabica, C. canephora and C. liberica) were introduced from Africa in the late 19th century, they survived in the wild and spontaneously cross-hybridized. Coffee species were originally planted in native forest in association with leguminous trees (mostly introduced species) to improve their growth. Thus the canopy cover over rustic shade coffee plantations is heterogeneous with a majority of large crowns, attributed to leguminous trees. The aim of this study was to identify suitable areas for coffee inter-specific hybridization in New Caledonia using field based environmental parameters and remotely sensed predictors. Due to the complex structure of tropical vegetation, remote sensing imagery needs to be spatially accurate and to have the appropriate bands for monitoring vegetation cover. Quickbird panchromatic (black and white) imagery at 0.6 to 0.7 m spatial resolutions and multispectral imagery at 2.4 m spatial resolution were pansharpened and used for this study. The two most suitable remotely sensed indicators, canopy heterogeneity and tree crown size, were acquired by the sequential use of tree crown detection (neural network), image processing (such as textural analysis) and classification. All models were supervised and trained on learning data determined by human expertise. The final model has two remotely sensed indicators and three physical parameters based on the Digital Elevation Model: elevation, slope and water flow accumulation. Using these five predictive variables as inputs, two modelling methods, a decision tree and a neural network, were implemented. The decision tree, which showed 96.9% accuracy on the test set, revealed the involvement of ecological parameters in the hybridization of Coffea species. We showed that hybrid zones could be characterized by combinations of modalities, underlining the complexity of the environment concerned. For instance, forest heterogeneity and large crown size, steep slopes (> 53.5%) and elevation between 194 and 429 m asl, are favourable factors for Coffea inter-specific hybridization. The application of the neural network on the whole area gave a predictive map that distinguished the most suitable areas by means of a nonlinear continuous indicator. The map provides a confidence level for each area. The most favourable areas were geographically localized, providing a clue for the detection and conservation of favourable areas for Coffea species neo-diversity.     

Independence of Containing Patterns Property and Its Application in Tree Pattern Query Rewriting Using Views

We show that several classes of tree patterns observe the independence of containing patterns property, that is, if a pattern is contained in the union of several patterns, then it is contained in one of them. We apply this property to two related problems on tree pattern rewriting using views. First, given view V and query Q, is it possible for Q to have an equivalent rewriting using V which is the union of two or more tree patterns, but not an equivalent rewriting which is a single pattern? This problem is of both theoretical and practical importance because, if the answer is no, then, to find an equivalent rewriting of a tree pattern using a view, we should use more efficient methods, such as the polynomial time algorithm of Xu and Özsoyoglu (2005), rather than try to find the union of all contained rewritings (which takes exponential time in the worst case) and test its equivalence to Q. Second, given a set S of views, we want to know under what conditions a subset S′ of S is redundant in the sense that for any query Q, the contained rewritings of Q using the views in S′ are contained in those using the views in S???S′. Solving this problem can help us to, for example, choose the minimum number of views to be cached, or better design the virtual schema in a mediated data integration system, or avoid repeated calculation in query optimization. For the first problem, we identify several classes of tree patterns for which the equivalent rewriting can be expressed as a single tree pattern. For the second problem, we present necessary and sufficient conditions for S′ to be redundant with respect to some classes of tree patterns. For both problems we consider extension to cases where there are rewritings using the intersection of multiple views and/or where a schema graph is present.     

谈专业竞赛对教学实践改革的促进作用

本文结合"数据结构"实践教学,探讨了高等教育大众化教育背景下计算机专业人才培养模式。通过介绍近年来我校参加的计算机专业竞赛,说明改革实践教学模式的必要性。     

Optimizing two-pass connected-component labeling algorithms

We present two optimization strategies to improve connected-component labeling algorithms. Taking together, they form an efficient two-pass labeling algorithm that is fast and theoretically optimal. The first optimization strategy reduces the number of neighboring pixels accessed through the use of a decision tree, and the second one streamlines the union-find algorithms used to track equivalent labels. We show that the first strategy reduces the average number of neighbors accessed by a factor of about 2. We prove our streamlined union-find algorithms have the same theoretical optimality as the more sophisticated ones in literature. This result generalizes an earlier one on using union-find in labeling algorithms by Fiorio and Gustedt (Theor Comput Sci 154(2):165–181, 1996). In tests, the new union-find algorithms improve a labeling algorithm by a factor of 4 or more. Through analyses and experiments, we demonstrate that our new two-pass labeling algorithm scales linearly with the number of pixels in the image, which is optimal in computational complexity theory. Furthermore, the new labeling algorithm outperforms the published labeling algorithms irrespective of test platforms. In comparing with the fastest known labeling algorithm for two-dimensional (2D) binary images called contour tracing algorithm, our new labeling algorithm is up to ten times faster than the contour tracing program distributed by the original authors.